//
//  Problem164.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/28.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 164. 最大间距 困难
 
 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

 示例 1:
     输入: nums = [3,6,9,1]
     输出: 3
     解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
 示例 2:
     输入: nums = [10]
     输出: 0
     解释: 数组元素个数小于 2，因此返回 0。

 提示:
 1 <= nums.length <= 10^5
 0 <= nums[i] <= 10^9
 */
class Problem164: NSObject {
    func maximumGap(_ nums: [Int]) -> Int {
        if nums.count < 2 {
            return 0
        }
        
        var list = nums
        tong(&list)
        
        var gap = Int.min
        for i in 1..<list.count {
            gap = max(gap, list[i] - list[i-1])
        }
        return gap
    }
    
    // 基数排序
    func tong(_ nums: inout [Int]) {
        // 求出最大值 O(n)
        let maxValue = nums.max()!
        
        // 位数
        var exp = 1
        
        // 数组：存储每一位比较后的排序 O(n)
        var buf = Array(repeating: 0, count: nums.count)
        
        while maxValue >= exp {
            // list记录：每一位上存储的个数
            var list = Array(repeating: 0, count: 10)
            // 遍历数组：取每一个数组对应位数的值
            for n in nums {
                list[(n / exp) % 10] += 1
            }
            // 这里目的是:排序,让存储在list[i]的值知道，它前面有几个数字
            for i in 1..<list.count {
                list[i] += list[i-1]
            }
            
            
            // 将数组先暂存到buf中
            for i in (0..<nums.count).reversed() {
                let digit = (nums[i] / exp) % 10
                buf[list[digit] - 1] = nums[i]        // 把数字n存储到buf中
                // 这里的目的是：如果2这个位置上有3个数字，上一步已经存储了一个数字，剩下的2个数字就签移动一位
                list[digit] -= 1
            }
            
            // 将buf复制到nums中
            for i in 0..<buf.count {
                nums[i] = buf[i]
            }
            
            print(exp)
            print(nums)
            // 每次*10: 取下一位
            exp *= 10
        }
    }
    
    /*
     思路：
     相邻数字的最大间距 >= ⌈(max−min)/(N−1)⌉
     最差的情况就是：每个值之间的间距是相同的，例如：1 3 5 7，那么最大间距也是每个值的间距=2
     只要有任何一个数字变大一点，那么最大的间距就会变大，也会 >= ⌈(max−min)/(N−1)⌉
     
     所以：这里要做的就是：先算出d=⌈(max−min)/(N−1)⌉, 然后根据最大值和最小值，按照d平均分割成几块
     然后把数组内的数字，放到每一块内，每一块内数字的间距肯定小于d，所以，最大间距是2个项链的块进行比较，
     所以每一块只要记录一下该块内的最大值和最小值就行
     */
    func maximumGap2(_ nums: [Int]) -> Int {
        if nums.count < 2 {
            return 0
        }
        
        let maxValue = nums.max()!
        let minValue = nums.min()!
        
        // 计算出d
        let d = max(1, (maxValue - minValue) / (nums.count - 1))
        
        let size = (maxValue - minValue) / d + 1
        
        // 创建一块空间
        var list = Array(repeating: Array(repeating: -1, count: 2), count: size)
        
        for n in nums {
            // 计算出n所对应的空间
            let index = (n - minValue) / d
            
            if list[index][0] == -1 {
                list[index][0] = n
                list[index][1] = n
            } else {
                // 只存储这块空间内的最大值和最小值
                list[index][0] = min(list[index][0], n)
                list[index][1] = max(list[index][1], n)
            }
        }
        
        // 比较2块空间之间的最大值和最小值的比较
        var gap = Int.min
        var lastI = -1
        for i in 0..<list.count {
            if list[i][0] != -1 {
                if lastI == -1 {
                    lastI = i
                }
                gap = max(gap, list[i][0] - list[lastI][1])
                lastI = i
            }
        }
        
        return gap
    }
}
